package com.da.javatest.niuke.jianzhi;

import java.util.ArrayList;
import java.util.List;

import com.da.javatest.niuke.common.ListNode;

/**
 * @author chenlida
 * @date 2020/10/21 10:09
 * https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?
 * tpId=13&tags=&title=&diffculty=0&judgeStatus=0&rp=1
 */
public class C14Solution {
    public ListNode FindKthToTail(ListNode head, int k) {
        List<Integer> list = new ArrayList<>();
        while (head != null) {
            list.add(head.val);
            head = head.next;
        }
        if (list.size() == 0 || k > list.size()) {
            return null;
        }
        ListNode newHead = new ListNode(-1);
        ListNode node = newHead;
        for (int i = list.size() - k; i < list.size(); i++) {
            node.next = new ListNode(list.get(i));
            node = node.next;
        }
        return newHead.next;
    }

    public ListNode FindKthToTail2(ListNode head, int k) {
        //首先定义两个指向链表头的指针p  ,q;
        //先令一个指针指向第k节点，然后两个指针同时向后移动，
        //最后p指向的即为倒数第k个节点。当k为零或节点为空返回。
        ListNode p = head, q = head;

        while (p != null) {
            if (k <= 0) {
                q = q.next;
            }
            p = p.next;
            k--;
        }
        return k <= 0 ? q : null;
    }
}
